package previous.Test_0313;

import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //最长湍急流数组:要注意边界问题
    //f[i]:以i位置元素为结尾的所有子数组中，最后呈现“上升”状态下的最长湍流数组的长度；
    //g[i]:以i位置元素为结尾的所有子数组中，最后呈现“下降”状态下的最长湍流数组的长度；
    public int maxTurbulenceSize(int[] arr) {
        int n=arr.length;
        int[] f=new int[n];
        int[] g=new int[n];
        Arrays.fill(f,1);
        Arrays.fill(g,1);
        int ret=1;
        for (int i = 1; i < n; i++) {
            int a=arr[i-1];
            int b=arr[i];
            if(a>b){
                g[i]=f[i-1]+1;
            }
            if(a<b){
                f[i]=g[i-1]+1;
            }
            ret=Math.max(ret,Math.max(g[i],f[i]));
        }
        return ret;
    }
    //单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> hash=new HashSet<>();
        int n=s.length();
        boolean[] b=new boolean[n+1];
        b[0]=true;
        //处理下标映射关系
        s=" "+s;
        for (int i = 1; i <= n; i++) {
            //j>=1
            for (int j = i; j >=0 ; j--) {
                if(b[j-1] && hash.contains(s.substring(j,i+1))){
                    b[i]=true;
                    break;
                }
            }
        }
        return b[n];
    }
    //环绕字符串中的唯一子字符串
    //dp[i]:以i结尾有多少个子窜
    public int findSubstringInWraproundString(String s) {
           int n=s.length();
           if(n==1) return 1;
           int[] dp=new int[n];
           char[] c=s.toCharArray();
           Arrays.fill(dp,1);
           int ret=1;
        for (int i = 1; i < n; i++) {
            if(c[i-1]+1==c[i] || c[i-1]=='z' && c[i]=='a'){
                dp[i]+=dp[i-1];
                ret=Math.max(ret,dp[i]);
            }
        }
        return ret;
    }
}
